Run length encoding schemes for compressing digital video streams are a known method of reducing the bandwidth required to transmit video over a transmission medium. In run-length encoding, pixels of a certain color value are transmitted by identifying a copy command rather than the actual pixel color itself. Ideally, with run-length encoding, multiple consecutive pixels of a common color can be defined by one (or a few) commands indicating, essentially, that a run of X length of common pixel colors can be drawn using a known color as the copy standard. Thus, rather than sending a stream of information identifying independent colors of consecutive pixels, the encoder issues a command to draw X number of pixels of a previously identified pixel color.
The difference in the amount of bandwidth required between individual pixel identification and run length encoding can be substantial, especially in the computer arts, where long lengths of pixels are the same color (for example, background). As described in the Dambrackas Application, several different ways of run length encoding can be envisioned, such as copying a run from a pixel to the left of the run, copying a run from a pixel in a previous frame, copying a run from a pixel above the first pixel in the run, or other such methods.
The present invention can be employed in any kind of run length encoding scheme, including for example, the run length encoding scheme of the Dambrackas application.
As those of ordinary skill in the art will understand, pixel colors are represented by a color space, typically an RGB color space so that any particular color in a color palette can be represented by a value of red, combined with a value of blue, combined with a value of green. The number of bits available for each one of the color components (R, G, and B) will define the depth or richness of the color palette. The present invention is not limited in any way to the number of bits provided by the particular color palette, but for simplicity and purposes of explanation only, the present invention will be described with respect to an eight bit per color RGB color space.
In FIG. 1, this eight bit per component color scheme is shown as orthogonal definitions of a 8×8×8 RGB color matrix. Every color in the color palette can be defined by a location within the orthogonal projections as (1) a value for R between 0x00 and 0xFF, (2) a value of G between 0x00 and 0xFF, and (3) a value of B between 0x00 and 0xFF. In uncompressed digital video, each pixel is defined by its unique 8×8×8 orthogonal location. Because screens of information can include millions of pixels, such video schemes require huge bandwidths for communication.
Thus, for the scan line of pixels shown in FIG. 3, the prior art of FIG. 4 attempts to identify each individual pixel color C1, C2, C3, etc. as individual triplets of bytes of the pixel information shown in FIG. 1. That is, in FIG. 4, the pixel color C1 is identified as an independent triplet of bytes with a header H, an eight-bit R component (Rox), an eight-bit green component (Gox), and an eight-bit blue component (Box) effectively identifying a single color in the 8×8×8 matrix of FIG. 1. The next triplet of bytes following the C1 triplet is the C2 triplet independently identifying the pixel color C2 in a manner similar to that shown in C1. Similarly, subsequent pixel colors C3, C4, etc. are identified by their own independent triplets of bytes. As one can see in FIG. 4, the pixel scan line of FIG. 3 is being identified by a stream of bytes that are uncompressed. With potentially millions of pixels per monitor screen and rapid refresh rates, the number of bytes required to employ the uncompressed video of FIG. 4 makes it essentially unworkable.
Known run length encoding, which compresses the video of FIG. 4 into a fewer number of bytes, is shown in FIG. 5. In this example, suppose that C1-C7 are the same color (for example in a background scan portion). In the example of FIG. 5, the first pixel color C1 in the scan line of FIG. 3 is encoded as an independent triplet of bytes (for each of the R, G, and B components), just like it was in the uncompressed video of FIG. 4. The C1 color, that is now known to the decoder at the monitor end, then becomes a standard by which the next six subsequent pixel colors C2-C7 (which in this example are the same color as C1) are identified by a single RLE (run length encoding) byte comprised of a header, a copy left (CL) command, and a payload identifying the run length of six pixels. The encoding of FIG. 5 communicates all the information needed to transmit the exact seven colors in the scan line of FIG. 3 with a first triplet of bytes followed by a single RLE byte, where the embodiment of FIG. 4 required seven triplets of bytes.
The embodiment of FIG. 5 works very well as long as the color encoder is able to identify long runs of exact match colors. Thus, in the example described above with respect to FIG. 5, the colors C1-C7 were assumed to be identical. A problem occurs, however, when the colors C1-C7 are identical in fact, but the encoder does not recognize them as identical. Such mistaken identity of colors usually occurs due to noise intrusion. Thus, if the encoder recognizes C2, C4 and C6 as even minutely different colors as C1, C3 and C5, the run length encoding will be thwarted because the encoder will not recognize the C1-C7 scan portion as a true run of identical colors. This can occur even when the encoder inaccurately perceives C2, C4 and C6 as neighbors to C1, C3 and C5 in orthogonal location (FIG. 1).
The present invention liberalizes the identification of matches among consecutive pixels so run lengths of matching colors will not be interrupted by certain noise conditions.